The present invention relates to a technique for ensuring security of digital signature, data encryption, etc. in a computer network, and particularly to a method of converting a message to a hash value which is difficult to inversely convert.
A public key cipher system has been known as an encryption system for data such as electronic mail which is sent and received through a network. The processing flow based on the public key cipher system is as follows:
(1) A user beforehand distributes to transmitters a public key for encrypting an electronic mail to be sent to the user.
(2) A transmitter who wishes to send the electronic mail to the user encrypts the electronic mail by using the public key which is distributed from the user who is the intended recipient of the electronic mail, and then transmits the encrypted electronic mail to the destination of the electronic mail.
(3) The user decrypts the encrypted electronic mail by using the user""s own secret key (having a numeric value different from the public key) when receiving the encrypted electronic mail which is encrypted by the public key distributed by himself/herself.
This public key cipher system has been applied not only to a data encryption technique, but also to a digital signature technique which is a technique for electrically verifying legitimacy of a contract or the like in electronic commerce using a network.
However, a lot of time is needed if a digital signature for a long message is generated by using only the public key cipher in the digital signature technique. Therefore, there has been proposed a method of temporarily compressing a message to shortened data and then generating a digital signature for the compressed data.
Here, for this type of data compression, it is unnecessary to compress the data so that an original message can be restored from the compressed data unlike normal data compression, however, it is necessary to compress the data so that the compressed data has a kind of encryption characteristic. A hash function has been proposed to implement such compression.
A message for an electronic commerce document or the like, for example, Document A: xe2x80x9cTo Taro and Co. Esq., I will purchase a car (catalog No. 1443) at one million and forty thousand yen. Mar. 10, 1996 Yoshiuraxe2x80x9d is input data to the hash function. There is no upper limit to the length of the input data.
The hash function subjects the input data to processing like encryption conversion to compress the input data to data having a fixed short length. For example, hash value: 283AC9081 E83D5B28977 is an output of the hash function.
This hash value is called a message digest or a finger print, and ideally substantially only one hash value exists for one input data (message) in the world. In order to guarantee that xe2x80x9csubstantially only one exists in the worldxe2x80x9d, it is generally recognized that the length of the hash value must be set to at least about 128 bits. More specifically, the hash function must have the following characteristics.
(1) One-way Property
When an output value of a hash function is given, it must be computationally difficult to determine another message which brings the same output value as the above output value.
For example, it is assumed that the birthday of Kazuo is February 22nd. In order to search for another person whose birthday is coincident with Kazuo""s birthday, it is statistically sufficient to investigate the birthdays of about 183 (365/2) persons.
The same is satisfied even when the person is replaced by a message and the birth day is replaced by a hash value. That is, if the length of the hash value is set to 160 bits, the hash value can have any one of 2160 possible values (i.e., the total number of possible hash values is equal to 2160). In order to search another message having the same hash value as a message concerned, it is required to investigate messages of 2160/2 (=2159), and this is computationally difficult.
(2) Collision Free Property
The message and the hash value may be any values (i.e., no limitation is imposed on the message and the hash value). At any rate, it must be computationally difficult to find out two different messages which have the same hash value.
For example, when any two persons having the same birthday are required to be found out, the birthdays of about 24 persons (=365xc2xd) need to be investigated in probability.
This is also satisfied even when the person is replaced by the message and the birth day is replaced by the hash value. That is, if the length of the hash value is set to 160 bits, in order to find out two different messages (any messages are possible) having the same hash value, it is necessary to investigate a set of messages of about 2160/2=280 on average. This number is smaller that that in the case of the one-way property, but this value is still computationally difficult. Various methods have been proposed to implement the hash function which requires the above characteristics, and at present a method of repeating character-substitution and transposition to obtain hash values have mainly been used. The following paper 1 discloses the processing principle of the method:
ISO/IEC 10118-2, xe2x80x9cInformation technologyxe2x80x94Security Techniquesxe2x80x94Hash-functions: Part 2: Hash-functions using an n-bit block encryption algorithmxe2x80x9d (1994)
The hash function as disclosed in the paper 1 will be described with reference to FIG. 27.
The left side of FIG. 27 is a diagram showing the processing flow of a general hash function, and the right side of FIG. 27 is a diagram showing the processing flow when an encryption function such as DES (Data Encryption Standard) is used for character-substitution/transposition repeating processing 3005 shown in the left side of FIG. 27.
As shown at the left side of FIG. 27, a message 3001 to be compressed is divided into a first section P13002, a second section P23003, . . . , for every predetermined length, and these sections are successively input to the hash function 3007.
The hash function 3007 subjects the first section P13002 to the character-substitution/transposition repeating processing 3005 by using an initial value 3004 as a parameter, thereby calculating a first intermediate output.
Subsequently, the hash function subjects the second section P23003 to the character-substitution/transposition repeating processing 3005 by using the first intermediate output as a parameter (in place of the initial value 3004), thereby calculating a second intermediate output.
The above processing is repeated until the data of the final section is input, and the finally calculated intermediate output is used as a hash value Hash 3006.
Here, in the paper 1, an encryption function (block encryption) such DES of USA encryption standard is used for the character-substitution/transposition repeating processing 3005. Such a hash function is called a xe2x80x9chash function using block encryptionxe2x80x9d, and it has been standardized in ISO (International Organization for Standardization).
The xe2x80x9chash function using block encryptionxe2x80x9d will be described below.
As shown at the right side of FIG. 27, the first section P13002 is input to the encryption function 3009 with a parameter which is obtained by converting the initial value 3004 with a conversion function 3008. Exclusive OR 3010 is conducted between the encryption result based on the encryption function 3009 and the first section P13002 bit by bit, thereby calculating the first intermediate output based on the character-substitution/transposition repeating processing 3005.
Subsequently, the first intermediate output is fed back and then converted with the conversion function 3008. Thereafter, by using the first intermediate output thus converted as a parameter, the second section P23003 is input to the encryption function 3009. The exclusive OR 3010 is conducted between the encryption result based on the encryption function 3009 and the second section P23003 bit by bit, thereby calculating the second intermediate output based on the character-substitution/transposition repeating processing 3005.
The above processing is repeated until the data of the final section is input, and the finally-calculated intermediate output is used as the hash value Hash 3006.
When DES or the like is used for the encryption function 3009 in the xe2x80x9chash function using block encryptionxe2x80x9d shown at the right side of FIG. 27, the length of each section of the first section P13002, the second section P23003, . . . , and the length of the output of the character-substitution/transposition repeating processing 3005 are respectively equal to 64 bits, and thus the length of the hash value Hash 3006 is equal to 64 bits.
The feature of the xe2x80x9chash function using block encryptionxe2x80x9d resides in that the length of each section P13002, P23003, . . . of the message is equal to the length of the output of the character-substitution/transposition repeating processing 3005.
A hash function which does not use any encryption function such as DES in the character-substitution/transposition repeating processing 3005 is proposed. Such a hash function is called a xe2x80x9cspecial-purpose hash functionxe2x80x9d, and there are known MD5 which is an internet standard, SHA-1 and RIPEMD-16 which are being standardized in ISO, etc.
Of these special-purpose hash functions, MD5 is disclosed in the following paper 2:
R. Rivest, xe2x80x9cThe MD5 Messagexe2x80x94Digest Algorithm, xe2x80x9cIETF RFC 1321 (1992) The processing flow of MD5 itself is the same as shown at the left side of FIG. 27, and it will be described with reference to the left side of FIG. 27.
First, a message 3001 to be compressed is divided into a first section P13002, a second section P23003, . . . every 512 bits, and these sections are successively input to the hash function 3007.
The hash function 3007 subjects the first section P13002 to simple character-substitution/transposition repeating processing 3005 by using an initial value 3004 of 128 bits as a parameter, thereby calculating a first intermediate output of 128 bits.
Subsequently, by using the first intermediate output as a parameter (in place of the initial value 3004), the hash function 3007 subjects the second section P23003 to the simple character-substitution/transposition repeating processing 3005, thereby calculating a second intermediate output of 128 bits.
The above processing is repeated until the data of the final section is input, and the finally-calculated 128-bit intermediate output is used as a hash value Hash 3006.
The feature of the xe2x80x9cspecial-purpose hash functionxe2x80x9d resides in that the length of the output of the character-substitution/transposition repeating processing 3005 is shorter than the length of each section P13002, P23003, . . . of the message.
The above prior arts have the following problems.
(1) Problem of Hash function which has been hitherto proposed
{circle around (1)}. Problem of xe2x80x9chash function using block encryptionxe2x80x9d
As described above, the xe2x80x9chash function using block encryptionxe2x80x9d uses an encryption function (block encryption) such as DES. In the block encryption, the data length of each of the input data and the output data is set to 64 bits. Therefore, the length of the hash value is equal to 64 bits. Further, in order to guarantee that xe2x80x9csubstantially only one hash value exists in the worldxe2x80x9d for one input data (message), it is believed that the length of the hash value must be set to about 128 bits or more as described above.
Accordingly, when a hash value of 128 bits is obtained in the xe2x80x9chash function using block encryptionxe2x80x9d, it is necessary to perform the block encryption processing on each input data (64 bits) to the block encryption twice while varying the initial value or the like. That is, it is necessary to calculate the output (64 bits) twice for each input data (64 bits) to the block encryption. This reduces the processing speed of generating hash values.
{circle around (2)}. Problem of xe2x80x9cspecial-purpose hash functionxe2x80x9d
According to the xe2x80x9cspecial-purpose hash functionxe2x80x9d, unlike the xe2x80x9chash function using block encryptionxe2x80x9d, a hash value of 128 bits can be obtained without performing the character-substitution/transposition repeating processing twice for each data into which the message is divided.
However, in the xe2x80x9cspecial-purpose hash functionxe2x80x9d, each data into which the message is divided is subjected to the simple character-substitution/transposition repeating processing to obtain hash values as described above. Here, the length of the output value of the character-substitution/transposition repeating processing (128 bits in the above case) is shorter than the length of the input value (512 bits in the above case). That is, the compression is performed in the character-substitution/transposition repeating processing.
Therefore, in the case where the message is divided into plural data every 512 bits, when there are assumed two messages in which the data of only the final sections thereof are different, in a process of compressing the data (512 bits) of the final section to the output of 128 bits through the character-substitution/transposition repeating processing, the outputs (i.e., hash values) of the two messages are coincident with each other with high probability. This deteriorates the collision free property.
{circle around (3)}. The problems of {circle around (1)}, {circle around (2)} also occur not only in the case where the hash function is applied to the digital signature, but also in other cases. For example, the same problems occur in a case where the hash function is applied to a data encryption system.
(1) Problem of public key cipher system
{circle around (1)}. A lot of processing time is needed when long data are encrypted by using the public key cipher.
{circle around (2)}. In the case where the public key cipher system is applied to the data encryption for electronic mail, etc., when the same electronic mail is transmitted to plural destinations with encryption, a transmitter must carry out the encryption processing on the electronic mail for every destination by using public keys which are distributed from the plural destinations in advance. That is, the encryption processing of the electronic mail must be repeated plural times, number being equal to the number of destinations.
On the other hand, when a receiver loses a secret key due to his/her erroneous erasure of the secret key from a file, the recipient cannot encrypt an encrypted electronic mail which is transmitted to the recipient while encrypted with a public key which was distributed to the sender by the recipient.
In view of the above condition, the object of the present invention is to rapidly generate hash values, keys, and cipher text which have a high degree of data scrambling. Further, another object of the present invention is to enable decryption of a personally sent encryption data by the cooperation of more than two other recipients even when the secret key is lost because of erroneous erasing from the file etc.
The present invention has been implemented in view of the situation, and according to a first aspect of the present invention, a hash value generating method which is used for digital signature or data encryption comprises:
a first step for dividing target data into at least two blocks;
a second step for performing character-substitution and/or transposition processing on any one of the at least two blocks obtained in the first step;
a third step for performing multiplication on the data obtained in the second step so that the multiplication result is longer than the data length of the data concerned;
a fourth step for further dividing the data obtained in the third step into at least two blocks; and
a fifth step for performing character-substitution and/or transposition processing on each of the at least two blocks obtained in the fourth step.
In the hash value generating method of the first aspect of the present invention, during the process of generating hash values, multiplication is such that the length of the output value is longer than that of the input value as described above is performed. According to the multiplication processing, each bit of the output value is affected by each bit of the input value, so scrambling of data can be performed with high efficiency.
The multiplication processing, particularly the processing speed thereof, is enhanced due to recent developments in the field of microprocessors. Accordingly, hash values having a high degree of data scrambling can be generated rapidly.
Further, according to a second aspect of the hash value generating method of the present invention, a hash value generating method which is used for digital signature or data encryption comprises:
a first step for dividing target data into at least two blocks; and
a second step for subjecting at least one of the at least two blocks obtained in the first step to an injection extension transformation in which an output value is absolutely different if an input value is different (injection) and the length of the output value is longer than the length of the input value (extension).
According to the second aspect of the hash value generating method of the present invention, during the hash value generating process, the injection extension transformation is performed so that the length of the output is set to be longer than that of the input, and if the input value is different, the output value is absolutely different. Therefore, a hash value having high collision free property, that is, a safe hash value, can be generated.
Here, the target data may be mixed with the initial value which is used as a parameter in the injection extension transformation and then input to the first step element, thereby reducing the probability that the same hash value is introduced for different initial values (i.e., the probability of occurrence of initial value collision).
Further, the target data which are input to the first step may be input to the first step again, thereby reducing the probability that the same hash value is introduced for different messages (i.e., the probability of occurrence of message collision).
According to a third aspect of the present invention, a data encryption method for encrypting data having a fixed length and outputting encryption data having a fixed length, comprises:
a first step for subjecting target data to character-substitution and/or transposition processing;
a second step for subjecting data obtained in the first step to such multiplication processing that the multiplication result is longer than the data length of the data concerned;
a third step for dividing the data obtained in the second step into at least two blocks; and
a fourth step for performing character-substitution and/or transposition processing on each of the at least two blocks obtained in the third step.
In the data encryption method of the third aspect of the present invention, during the data encryption process, the multiplication is performed so that the length of the output is longer than that of the input value, and thus the scrambling of the data can be efficiently performed.
Further, according to a fourth aspect of the present invention, a data encryption method using public key cipher for encrypting plain text by using a public key, comprises:
a first step for encrypting plain text by using as a parameter data which are obtained by converting a first public key; and
a second step for generating a data value satisfying a relational equation between data based on at least one second public key and the data obtained by converting the first public key, the relational equation being capable of directly or indirectly determine the data obtained by converting the first public key if the data based on the second public key are known, wherein the data value obtained in the second step is added to cipher text obtained in the first step as encryption data to be transmitted.
Further, according to a fifth aspect of the present invention, a data decryption method which is paired with the data encryption method of the fourth aspect of the present invention, comprises:
A third step for determining the data based on the second public key from a secret key which is paired with the second public key;
A fourth step for determining the data obtained by converting the first public key on the basis of the data value added to the cipher text and the data obtained in the third step; and
A fifth step for decrypting the cipher text by using the data obtained in the fourth step as a parameter.
According to the data encryption method of the fourth aspect of the present invention and the data decryption method of the fifth aspect of the present invention which is paired with the data encryption method, a person having a secret key which is paired with the second public key can gain the data obtained by converting the first public from the data value generated in the second step alone or in cooperation with another person having a secret key which is paired with another second public key.
Accordingly, not only any person having a secret key which is paired with the first public key, but also any person having a secret key which is paired with the second public key can decrypt the data.
This means that when the same electronic mail is transmitted to plural destinations with encryption, it is unnecessary for a transmission side to encrypt the electronic mail while using public keys distributed from the respective destinations one by one.